COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	folio 621 galley 1
C00020 00003	folio 624 galley 2
C00040 00004	folio 629 galley 3
C00054 00005	folio 632 galley 4
C00070 00006	folio 635 galley 5
C00085 00007	folio 638 galley 6
C00097 00008	folio 643 galley 7
C00114 ENDMK
C⊗;
folio 621 galley 1
    0  {U0}{H10L12M29}58320#Computer Programming!(A.-W./Knuth)!ch. 
    2  4!f. 621!g. 1D|'{A12}|π!|4|4|4|4An even better 
    8  scheme for large |εn, |πdiscovered by Volker 
   15  Strassen in 1968, is based on the fact that the 
   25  product of 2|4α⊗↓|42 matrices can be evaluated 
   32  with only 7 multiplications, without relying 
   38  on the commutativity of multiplication as in 
   45  (35). Therefore 2|εn|4α⊗↓|42n |πmatrices can 
   50  be partitioned into four |εn|4α⊗↓|4n |πmatrices 
   56  and the idea can be used recursively to obtain 
   65  the product of |ε2|gk|4α⊗↓|42|gk |πmatrices with 
   71  only 7|ε|gk |πmultiplications instead of |ε(2|gk)|g3|4α=↓|48
   76  |gk. |πStrassen's original 2|4α⊗↓|42 identity 
   81  |ε[Numer. Math. |≡1|≡3 (1969), 354<356] |πused 
   87  7 multiplications and 18 additions; S. Winograd 
   94  later discovered the following more economical 
  100  formula:|'{A6}|h|ε|9|1|1a!b|9|1|1|9|1|1A!D|9|1|1|4α=↓|4|9|1|
  101  1|∂w|4α+↓|4(a|4α_↓|4c)(D|4α_↓|4C)|4α_↓|4d(A|4α_↓|4B|4α_↓|4C|
  101  4α+↓|4D)!!|∂kplolhjk.,|E|n|'|↔|(a!b|d5c!d|)|↔s|↔a|(A!C|d5B!D
  102  |)|↔s|4α=↓|4|↔a|'{B26}|LaA|4α+↓|4bB|Lw|4α+↓|4(c|4α+↓|4d)(C|4
  103  α_↓|4A)|4α+↓|4(a|4α+↓|4b|4α_↓|4c|4α_↓|4d)D>{A2}|Lw|4α+↓|4(a|
  104  4α_↓|4c)(D|4α_↓|4C)|4α_↓|4d(A|4α_↓|4B|4α_↓|4C|4α+↓|4D)|Lw|4α
  104  +↓|4(a|4α_↓|4c)(D|4α_↓|4C)|4α+↓|4(c|4α+↓|4d)(C|4α_↓|4A)>
  105  {A4}(36)|?{A6}|πwhere |εw|4α=↓|4aA|4α_↓|4(a|4α_↓|4c|4α_↓|4d)
  107  (A|4α_↓|4C|4α+↓|4D). |πIf intermediate results 
  111  are appropriately saved, (36) involves 7 multiplications 
  118  and only 15 additions; by induction on |εk, |πwe 
  127  can multiply |ε2|gk|4α⊗↓|42|gk |πmatrices with 
  132  |ε7|gk |πmatrices with |ε7|gk |πmultiplications 
  137  and |ε5(7|gk|4α_↓|44|gk) |πadditions. The total 
  142  number of operations needed to multiply |εn|4α⊗↓|4n 
  149  |πmatrices has therefore been reduced from order 
  156  |εn|g3 |πto |εO(n|π|gl|gg|1|1|g7)|4α=↓|4|εO(n|g2|g.|g8|g0|g7
  158  |g4). |πStrassen showed that |εA |πsimilar reduction 
  165  applies also to the evaluation of determinants 
  172  and matrix inverses; cf. J. R. Bunch and J. E. 
  182  Hopcroft, |εMath. Comp. |≡2|≡8 (1974), 231<236.|'
  188  |π!|4|4|4|4These theoretical results are quite 
  193  striking, but from a practical standpoint they 
  200  are of limited use because |εn |πmust be very 
  209  large before we overcome the e=ect of additional 
  217  bookkeeping costs. Richard Brent [Stanford Computer 
  223  Science report CS157 (March, 1970), see also 
  230  |εNumer. Math. |≡1|≡6 (1970), 145<156] |πfound 
  236  that a careful implementation of Winograd's scheme 
  243  (35), with appropriate scaling for numerical 
  249  stability, became better than the conventional 
  255  scheme only when |εn|4|¬R|440, |πand it saved 
  262  7 percent of the running time when |εn|4α=↓|4100. 
  270  |πFor complex arithmetic the situation was somewhat 
  277  di=erent; (35) became advantageous for |εn|4|¬Q|420, 
  283  |πand saved 18 percent when |εn|4α=↓|4100. |πHe 
  290  estimated that Strassen's scheme would not begin 
  297  to excel more than 60,000 entries, rarely occur 
  305  in practice (unless they are very sparse, when 
  313  other techniques apply).|'!|4|4|4|4By contrast, 
  318  the methods we shall discuss next are eminently 
  326  practical nd have found wide use. The |ε⊂nite 
  334  Fourier transform f |πof a complex-valued function 
  341  |εF |πof |εn |πvariables, over domains of |εm|β1,|4.|4.|4.|4
  348  ,|4m|βn |πelements, is de_ned by the equation|'
  355  {A6}|εf|1(s|β1,|4.|4.|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1|¬W
  355  m|β1|d.|4.|4.|4.|4.|4|d0|¬Et|βn|¬Wm|βn|)|4|πexp|↔a2|≤pi|↔a|(
  355  s|β1t|β1|d2m|β1|)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|(s|βnt|βn|d
  355  2m|βn|)|↔s|↔sF(t|β1,|4.|4.|4.|4,|4t|βn)|J!(37)|;
  356  {A6}|πfor |εo|4|¬E|4s|β1|4|¬W|4m|β1,|4.|4.|4.|4,|40|4|¬E|4s|
  357  βn|4|¬W|4m|βn; |πthe name ``transform'' is justi_ed 
  363  because we can recover the values |εF(t|β1,|4.|4.|4.|4,|4t|β
  369  n) |πfrom the values |εf|1(s|β1,|4.|4.|4.|4,|4s|βn), 
  374  |πas shown in exercise 13. In the important special 
  383  case that all |εm|βj|4α=↓|42, |πwe have|'{A6}|εf|1(s|β1,|4.|
  389  4.|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1,|4.|4.|4.|4,|4t|βn|¬E
  389  1|)|4(|→α_↓1)|urs|β1t|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4s|βnt
  389  |βn|)|)F(t|β1,|4.|4.|4.|4,|4t|βn)|J!(38)|;{A6}|πfor 
  391  |ε0|4|¬E|4s|β1,|4.|4.|4.|4,|4s|βn|4|¬E|41, |πand 
  393  this may be regarded as a simultaneous evaluation 
  401  of |ε2|gn |πlinear polynomials in 2|ε|gn |πvariables 
  408  |εF(t|β1,|4.|4.|4.|4,|4t|βn). |πA well-known 
  411  technique due to F. Yates |εThe Design and Analysis 
  420  of Factorial Experiments (|πHarpenden: Imperial 
  425  Bureau of Soil Sciences, 1937)] can be used to 
  434  reduce the number of additions implied in (38) 
  442  from |ε2|gn(2|gn|4α_↓|41) |πto |εn2|gn. |πYate's 
  447  method can be understood by considering the case 
  455  |εn|4α=↓|43: |πLet |εx|ur|)t|β1t|β2t|β3|)|4α=↓|4F(t|β1,|4t|β
  457  2,|4t|β3).|'{A6}{H6L7M29}|h|ε|∂x|β2|β2|β2!!|∂x|β1|β1|β1|4α⊗↓
  458  |4x|β1|β1|β1!!|∂x|β2|β2|β2|4α⊗↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β9
  458  |4α⊗↓|4x|β0|β0|β0!!|∂x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|4α⊗↓|4x|β0|
  458  β0|β0|4α=↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|4α=↓|4x|β0|β0|β0|4α=
  458  ↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|∂|E|n|'|>|πGiven|'
  461  First|4step!!|;Second|4step!!|;Third|4step|;>
  465  {A2}|εx|β0|β0|β0!!x|β0|β0|β0|4α+↓|4x|β0|β0|β1!!x|β0|β0|β0|4α
  465  +↓|4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β0|β0|β0
  465  |4α+↓|4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α+↓|4x|
  465  β1|β0|β0|4α+↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|
  465  'x|β0|β0|β1!!x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β1|β0|β0|4α+↓|4x
  466  |β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓
  466  |4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α+↓|4x|β1|β0
  466  |β0|4α_↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
  467  x|β0|β1|β0!!x|β1|β0|β0|4α+↓|4x|β1|β0|β1!!x|β0|β0|β0|4α_↓|4x|
  467  β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
  467  4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α+↓|4x|β1|β0|
  467  β0|4α+↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
  468  x|β0|β1|β1!!x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β1|β0|β0|4α_↓|4x|
  468  β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
  468  4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α+↓|4x|β1|β0|
  468  β0|4α_↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
  469  x|β1|β0|β0!!x|β0|β0|β0|4α_↓|4x|β0|β0|β1!!x|β0|β0|β0|4α+↓|4x|
  469  β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
  469  4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
  469  β0|4α_↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
  470  x|β1|β0|β1!!x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β1|β0|β0|4α+↓|4x|
  470  β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
  470  4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
  470  β0|4α+↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
  471  x|β1|β1|β0!!x|β1|β0|β0|4α_↓|4x|β1|β0|β1!!x|β0|β0|β0|4α_↓|4x|
  471  β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
  471  4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
  471  β0|4α_↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
  472  x|β1|β1|β1!!x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β1|β0|β0|4α_↓|4x|
  472  β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
  472  4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
  472  β0|4α+↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
  473  {A6}{H10L12M29}|πTo get from the ``Given'' to 
  479  the ``First step'' requires four additions and 
  486  four subtractions; and the interesting feature 
  492  of Yates's method is that exactly the same transformation 
  501  which takes us from ``Given'' to ``First step'' 
  509  will take us from ``First step'' to ``Second 
  517  step'' and from ``Second step'' to ``Third step.'' 
  525  In each case we do four additions, then four 
  534  subtractions; and after three steps we have the 
  542  desired Fourier transform |εf|1(s|β1, s|β2, s|β3) 
  548  |πin the place originally occupied by |εF|1(s|β1, 
  555  s|β2, s|β3)*3|'|π!|4|4|4|4This special case is 
  561  often called the |εWalsh transform |πof 2|ε|gn 
  568  |πdata elements, since the corresponding pattern 
  574  of signs was studied by J. L. Walsh |ε[Amer. 
  583  J. Math. |≡4|≡5 (1923), 5<24]. |πNote that the 
  591  number of sign changes from left to right in 
  600  the ``Third step'' above assumes the respective 
  607  values 0, 7, 3, 4, 1, 6, 2, 5. Walsh observed 
  618  that there will be exactly 0, 1,|4.|4.|4.|4,|42|ε|gn|4α_↓|41
  624   |πsign changes in some order in the general 
  633  case, so the coe∃cients provide discrete approximations 
  640  to sine waves with various frequencies. (See 
  647  H. F. Harmuth, |εIEEE Spectrum |≡6|≡, 11 (|πNov. 
  655  1969), 82<91 for applications of this property, 
  662  and see Section 7.2.1 for further discussion 
  669  of the Walsh coe∃cients.)|'!|4|4|4|4Yates's method 
  675  can be generalized to the evaluation of any _nite 
  684  Fourier transform, and, in fact, to the evaluation 
  692  of any sum which can be written|'{A6}|εf|1(s|β1,|4s|β2,|4.|4
  699  .|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1|¬Wm|β1|d.|4.|4.|4.|4|d
  699  0|¬Et|βn|¬Wm|βn|)|4g|β1(s|β1,|4s|β2,|4.|4.|4.|4,|4s|βn|4t|β1
  699  )g|β2(s|β2,|4.|4.|4.|4,|4s|βn,|4t|β2)|4|¬O|4|¬O|4|¬O|'
  700  {A4}g|βn(s|βn,|4t|βn)F(t|β1,|4t|β2,|4.|4.|4.|4,|4t|βn),|40|4
  700  |¬E|4s|βj|4|¬W|4m|βj,!(29)|?{A6}|πfor given functions 
  704  |εg|βj(s|βj,|4.|4.|4.|4,|4s|βn,|4t|βj). |πProceed 
  706  as follows:|'{A6}|h|εf|g[|g2|g](s|βn|βα_↓|β1,|4s|βn,|4t|β1,|
  708  4.|4.|4.|4,|4t|βn|βα_↓|β2|4|∂oikolp|E|n|'| f|g[|g0|g](t|β1,|
  709  4t|β2,|4t|β3,|4.|4.|4.|4,|4t|βn)|4|Lα=↓|4F(t|β1,|4t|β2,|4t|β
  709  3,|4.|4.|4.|4,|4t|βn);>{A6}| f|g[|g1|g](s|βn,|4t|β1,|4t|β2,|
  710  4.|4.|4.|4,|4t|βn|βα_↓|β1)|4|Lα=↓|4|↔k|uc|)0|¬Et|βn|¬Wm|βn|)
  710  |4g|βn(s|βn,|4t|βn)f|g[|g0|g](t|β1,|4t|β2,|4.|4.|4.|4,|4t|βn
  710  );|'{A6}| f|g[|g2|g](s|βn|βα_↓|β1,|4s|βn,|4t|β1,|4.|4.|4.|4,
  711  |4t|βn|βα_↓|β2)|4|Lα=↓|4|↔k|uc|)0|¬Et|βn|βα_↓|β1|¬Wm|βn|βα_↓
  711  |β1|)|4g|βn|βα_↓|β1(s|βn|βα_↓|β1,|4s|βn,|4t|βn|βα_↓|β1)f|g[|
  711  g1|g](s|βn,|4t|β1,|4.|4.|4.|4,|4t|βn|βα_↓|β1);|'
  712  {A6}!|¬O|4|¬O|4|¬O|'| f|g[|gn|g](s|β1,|4s|β2,|4s|β3,|4.|4.|4
  713  .|4,|4s|βn)|4|Lα=↓|4|↔k|uc|)0|¬Et|β1|¬Wm|β1|)|4g|β1(s|β1,|4.
  713  |4.|4.|4,|4s|βn,|4t|β1)f|g[|gn|gα_↓|g1|g](s|β2,|4s|β3,|4.|4.
  713  |4.|4,|4s|βn,|4t|β1);|'{A6}| | f|1(s|β1,|4s|β2,|4s|β3,|4.|4.
  714  |4.|4,|4s|βn)|4|Lα=↓|4f|g[|gn|g](s|β1,|4s|β2,|4s|β3,|4.|4.|4
  714  .|4,|4s|βn).|J!(40)>{A6}|Hβ*?{U0}{H10L12M29}58320#Computer 
folio 624 galley 2
  716  Programming!(A.-W./Knuth)!ch. 4!f. 624!g. 2D|'
  720  {A12}|πFor Yate's method as shown above, |εg|βj(s|βj,|4.|4.|
  726  4.|4,|4s|βn,|4t|βj)|4α=↓|4(α_↓1)|gs|rj|gt|rj; 
  727  f|g[|g0|g](t|β1,|4t|β2,|4t|β3) |πrepresents the 
  730  ``Given''; |εf|g[|g1|g](s|β3,|4t|β1,|4t|β2) |πrepresents 
  733  the ``First step''; etc. Whenever a sum can be 
  742  put into the form of (39), for reasonably simple 
  751  functions |εg|βj(s|βj,|4.|4.|4.|4,|4s|βn,|4t|βj), 
  753  |πthe scheme (40) will reduce the amount of computation 
  762  from order |εN|g2 |πto rougly the order |εN|4|πlog 
  770  |εN, |πwhere |εN|4α=↓|4m|β1,|4.|4.|4.|4m|βn; 
  773  |πfurthermore this scheme is ideally suited to 
  780  parallel computation. The important special case 
  786  of one-dimensional Fourier transforms is discussed 
  792  in exercise 14.|'!|4|4|4|4Let us consider one 
  799  more special case of polynomial evaluation. |εLagrange's 
  806  interpolation polynomial |πof order |εn, |πwhich 
  812  we shall write as|'{A6}|h|εu|g[|gn|g](x)|4|∂α=↓|4α+↓|4y|β1|4
  816  (x|β1|4α_↓|4x|β0)(x|β1|4α+↓|4x|β2)|4.|4.|4.|4(x|β1|4α+↓|4x|β
  816  n)|4α=↓|4.|4.|4.|E|n|;| u|g[|gn|g](x)|4|Lα=↓|4y|β0|4|((x|4α_
  817  ↓|4x|β1)(x|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn)|d2(x|β
  817  0|4α_↓|4x|β1)(x|β0|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|β0|4α_↓|4x
  817  |βn)|)>{A4}|L|4|4|4|4|4|1|1α+↓|4y|β1|4|((x|4α_↓|4x|β0)(x|4α_
  818  ↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn)|d2(x|β1|4α_↓|4x|β0)(
  818  x|β1|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|β1|4α_↓|4x|βn)|)|4α+↓|4|
  818  ¬O|4|¬O|4|¬O>{A4}|L|4|4|4|4|1|1α+↓|4y|βn|4|((x|4α_↓|4x|β0)(x
  819  |4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1)|d2(x|βn|
  819  4α_↓|4x|β0)(x|βn|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x|βn|4α_↓|4x|β
  819  n|βα_↓|β1)|)|4,|J!(41)>{A6}|πis the only polynomial 
  824  of degree |ε|¬En |πin |εx |πwhich takes on the 
  833  respective values |εy|β0,|4y|β1,|4.|4.|4.|4,|4y|βn 
  836  |πat the |εn|4α+↓|41 |πdistinct points |εx|4α=↓|4x|β0,|4x|β1
  841  ,|4.|4.|4.|4,x|βn. |π(For it is evident from 
  847  (41) that |εu|g[|gn|g](x|βk)|4α=↓|4y|βk |πfor 
  851  |ε0|4|¬E|4k|4|¬E|4n. |πIf |εf|1(x) |πis any such 
  857  polynomial of degree |ε|¬En, |πthen |εg(x)|4α=↓|4f|1(x)|4α_↓
  862  |4u|g[|gn|g](x) |πis of degree |ε|¬En, |πand 
  868  |εg(x) |πis zero for |εx|4α=↓|4x|β0,|4x|β1,|4.|4.|4.|4,|4x|β
  872  n; |πtherefore |εg(x) |πis a multiple of the 
  880  polynomial |ε(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x
  881  |4α_↓|4x|βn). |πThe degree of the latter polynomial 
  888  is greater than |εn, |πso |εg(x)|4α=↓|40.) |πIf 
  895  we assume that the values of a function in some 
  905  table are well-approximated by a polynomial, 
  911  Lagrange's formula (41) may there fore be used 
  919  to ``interpolate'' for values of the function 
  926  at points |εx |πnot appearing in the table. Unfortunately, 
  935  there seem to be quite a few additions, subtractions, 
  944  multiplications, and divisions in Lagrange's 
  949  formula; in fact, there are |εn |πadditions, 
  956  |ε2n|g2|4α+↓|42 |πsubtractions, |ε2n|g2|4α+↓|4n|4α_↓|41 
  959  |πmultiplications, and |εn|4α+↓|41 |πdivisions. 
  963  Fortunately (as we might suspect), improvement 
  969  is possible.|'|4|4|4|4!The basic idea for simplifying 
  976  (4) is to note that |εu|g[|gn|g](x)|4α_↓|4u|g[|gn|gα_↓|g1|g]
  981  (x) |πis zero for |εx|4α=↓|4x|β0,|4.|4.|4.|4,|4x|βn|βα_↓|β1;
  985   |πthus |εu|g[|gn|g](x)|4α_↓|4u|g[|gn|gα_↓|g1|g](x) 
  988  |πis a polynomial of degree |ε|¬En |πand a multiple 
  997  of |ε(x|4α_↓|4x|β0)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1). 
  999  |πWe conclude that |εu|g[|gn|g](x)|4α=↓|4|≤a|βn(x|4α_↓|4x|β0
 1002  )|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4u|g[|gn|gα_↓|
 1002  g1|g](x), |πwhere |ε|≤a|βn |πis a constant. This 
 1009  leads us to |εNewton's interpolation formula{A6}u|g[|gn|g](x
 1014  )|4α=↓|4|∂|≤a|βn(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|
 1014  4(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4|¬O|4|¬O|4|¬O|;
 1015  {A4}|Lα+↓|4|≤a|β2(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4α+↓|4|≤a|β1(x
 1015  |4α_↓|4x|β0)|4α+↓|4|≤a|β0,|J!(42)>{A6}|πwhere 
 1017  the |ε|≤a'|πs are some constants we should like 
 1025  to determine from |εx|β0,|4x|β1,|4.|4.|4.|4, 
 1029  x|βn,|4y|β0,|4y|β1,|4.|4.|4.|4,|4y|βn. |πNote 
 1031  that this formula holds for all |εn; |≤a|βk |πdoes 
 1040  not depend on |εx|βk|βα+↓|β1,|4.|4.|4.|4,|4x|βn,|4y|βk|βα+↓|
 1043  β1,|4.|4.|4.|4,|4y|βn. |πOnce the |ε|≤a'|πs are 
 1048  known, Newton's interpolation formula is conveneient 
 1054  for calculation, since we may generalize Horner's 
 1061  rule once again and write|'{A6}|εu|g[|gn|g](x)|4α=↓|4{H12}({
 1066  H10}(|¬O|4|¬O|4|¬O|4(|≤a|βn(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4|≤a|
 1066  βn|βα_↓|β1)(x|4α_↓|4x|βn|βα_↓|β2)|4α+↓|1|1|¬O|4|¬O|4|¬O)(x|4
 1066  α_↓|4x|β0)|4α+↓|4|≤a|β0{H12}){H10}.|;{A4}(43)|?
 1068  {A6}|πThis requires |εn |πmultiplications and 
 1073  |ε2n |πadditions. Alternatively, we may evaluate 
 1079  eachof the individual terms of (42) from right 
 1087  to left; with |ε2n|4α_↓|41 |πmultiplications 
 1092  and |ε2n |πadditions we thereby calculate all 
 1099  of the values |εu|g[|g0|g](x), u|g[|g1|g](x),|4.|4.|4.|4,|4u
 1103  |g[|gn|g](x), |πand this indicates whether or 
 1109  not the interpolation process is ``converging.''|'
 1115  !|4|4|4|4The |ε|≤a'|πs in Newton's formula may 
 1121  be found by computing the ``divided di=erences'' 
 1128  in the following tableau (shown for |εn|4α=↓|43):|'
 1135  {A6}}h10l7}|h|ε|∂y|β0|9|∂(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β1)
 1135  |4α+↓|4y|β2|9|∂(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β0)|4α=↓|4y|β
 1135  2|9|∂(y|β3|4α_↓|4y|β3)/(x|β3|4α_↓|4x|β0)|4α=↓|4y|9|1|E|n|;
 1136  |Ly|β0>|L|L(y|β1|4α_↓|4y|β0)/(x|β1|4α_↓|4x|β0)|4α=↓|4y|ur|↔0
 1137  |)1|)>|Ly|β1|L|L(y|ur|↔0|)2|)|4α_↓|4y|ur|↔0|)1|))/(x|β2|4α_↓
 1138  |4x|β0)|4α=↓|4y|β2>|L|L(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β1)|4
 1139  α=↓|4y|ur|↔0|)2|)|L|L(y|β3|4α_↓|4y|β2)/(x|β3|4α_↓|4x|β0)|4α=
 1139  ↓|4y|β3>|Ly|β2|L|L(y|ur|↔0|)3|)|4α_↓|4y|ur|↔0|)2|))/(x|β3|4α
 1140  _↓|4x|β1)|4α=↓|4y|β3>|L|L(y|β3|4α_↓|4y|β2)/(x|β3|4α_↓|4x|β2)
 1141  |4α=↓|4y|β3>|Ly|β3>{B7}(44)|?{A12}{A5}|π{H10L12M29}It 
 1145  is possible to prove that |ε|≤a|β0|4α=↓|4y|β0, 
 1151  |≤a|β1|4α=↓|4y|ur|↔0|)1|), |≤a|β2|4α=↓|4y|β2, 
 1153  |πetc., and that the divided di=erences have 
 1160  important relations to the derivatives of the 
 1167  function being interpolated; see exercise 15. 
 1173  Therefore the following calculation {H12}({H10}corresponding
 1177   to (44){H12}) {H10}may be used to obtain the 
 1186  |ε|≤a'|πs:|'{A6}!|4|4|4|4Start with |ε(|≤a|β0,|4|≤a|β1,|4.|4
 1189  .|4.|4,|4|≤a|βn)|4|¬L|4(y|β0,|4y|β1,|4.|4.|4.|4,|4y|βn); 
 1190  |πthen, for |εk|4α=↓|41,|42,|4.|4.|4.|4,|4n>!|4|4|4|4(|πin 
 1194  this order), set |εy|βj|4|¬L|4(y|βj|4α_↓|4y|βj|βα_↓|β1)/(x|β
 1197  j|4α_↓|4x|βj|βα_↓|βk) |πfor |εj|4α=↓|4n, n|4α_↓|41,|4.|4.|4.
 1200  |4,|4k>!|4|4|4|4|π(in this order).|'{A6}This 
 1205  process requires |f1|d32|)(|εn|g2|4α+↓|4n) |πdivisions 
 1209  and |εn|g2|4α+↓|4n |πsubtractions, so about three-fourths 
 1215  of the work implied in (41) has been saved.|'
 1224  !|4|4|4|4For example, suppose that we want to 
 1231  estimate |f3|d32|)*3 from the values of 0.*3, 1*3, 
 1239  2*3, and 3*3, using a cubic polynomial. The divided 
 1248  di=erences are|'|h|ε|∂x!!|∂y!!|∂y|¬S!!|∂y|¬C!!|∂y|9|1|∂|E|n|
 1250  ;|Lx|Ly|Ly|¬S|Ly|¬C|Ly>{A2}{H10L7M29}|L0|L1>|L|L|L0>
 1254  |L1|L1|L|L|f1|d32|)>|L|L|L1|L|L|f1|d33|)>|L2|L2|L|L|f3|d32|)
 1256  >|L|L|L4>|L3|L6>{A6}{H10L12M29}|πso |εu|g[|g0|g](x)|4α=↓|4u|
 1260  g[|g1|g](x)|4α=↓|41, u|g[|g2|g](x)|4α=↓|4|f1|d32|)x(x|4α_↓|4
 1261  1)|4α+↓|41, u|g[|g3|g](x)|4α=↓|4|f1|d33|)x(x|4α_↓|41)(x|4α_↓
 1262  |42)|4α+↓|4|f1|d32|)x(x|4α_↓|41)|4α+↓|41. |πSetting 
 1264  |εx|4α=↓|4|f3|d32|) |πgives α_↓|f1|d38|)|4α+↓|43|d38|)|4α+↓|
 1266  41|4α=↓|41.25; presumably the ``correct'' value 
 1271  is |ε|≤)(|f5|d32|))|4α=↓|4|f3|d34|){U20}|≤p|)|4|¬V|41.33.|'
 1273  |π!|4|4|4|4It is instructive to note that evaluation 
 1280  of the interpolation polynomial is just a special 
 1288  case of the Chinese remainder algorithm of Section 
 1296  4.3.2, since we know the value of |εu|g[|gn|g](x) 
 1304  |πmod the relatively prime polynomials |εx|4α_↓|4x|β0,|4.|4.
 1309  |4.|4,|4x|4α_↓|4x|βn. |π{H12}({H10}As we have 
 1313  seen above, |εf|1(x) |πmod |ε(x|4α_↓|4x|β0)|4α=↓|4f|1(x|β0).
 1317  {H12}) {H10}Under this interpretation, Newton's 
 1322  formula (42) |πis precisely the ``mixed radix 
 1329  representation'' of Eq. 4.3.2<24; and 4.3.2<23 
 1335  yields another way to compute |ε|≤a|β0,|4.|4.|4.|4,|4|≤a|βn 
 1341  |πusing the same number of operations as (44).|'
 1349  !|4|4|4|4By applying fast Fourier transforms, 
 1354  it is possible to reduce the running time for 
 1363  interpolation to |εO{H12}({H10}n(|πlog|4|εn)|g2{H12}){H10}, 
 1366  and a similar reduction can also be made for 
 1375  related algorithms such as the solution to the 
 1383  Chinese remainder problem and the evaluation 
 1389  of an |εn|πth degree polynomial at |εn |πdi=erenthppo*?ee 
 1397  polynomial at |εn |πdi=erent points; see E. Horowitz, 
 1405  |εInf. Proc. Letters |≡1 (1972), 157<163, |πR. 
 1412  Moenck and A. Borodin, |εJ. Comp. Syst. Sci. 
 1420  |≡8 (1974), 336<385, |πand A. Borodin, |εcomplexity 
 1427  of Sequential and Parallel Numerical algorithms, 
 1433  |πed. by J. F. Traub (New York: Academic Press, 
 1442  1973), 149<180). However, this must be regarded 
 1449  as a purely theoretical possibility at present, 
 1456  since the known algorithms have a rather large 
 1464  overhead factor.|'!|4|4|4|4A remarkable modi_cation 
 1469  of the method of divided di=erences, whioch applies 
 1477  to rational functions instead of polynomials, 
 1483  was introduced by T. N. Thiele in 1909. For a 
 1493  discussion of Thiele's method of ``reciprocal 
 1499  di=erences,'' see L. M. Milne-Thompson, |εCalculus 
 1505  of Finite Di∩erences (|πLondon: MacMillan, 1933), 
 1511  chapter 5; R. W. Floyd, |εCACM |≡3 (1960), 508.|'
 1520  {A12}|≡F|≡o|≡r |≡f|≡u|≡r|≡t|≡h|≡e|≡r |≡r|≡e|≡a|≡d|≡i|≡n|≡g|≡
 1522  .|9|4In this section we have barely scratched 
 1529  the surface of a very large subject in which 
 1538  many beautiful theories are emerging; a more 
 1545  comprehensive treatment appears in the book |εComputational 
 1552  Complexity of Algebraic and Numeric Problems 
 1558  |πby A. Borodin and I. Munro (New York: American 
 1567  Elsevier, 1975).|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'
 1570  {A12}{H9L11M29}|9|1|≡1|≡.|9|4|ε[|*/OC|\] |πWhat 
 1572  is a good way to evaluate an ``odd'' polynomial|'
 1581  {A6}|εu(x)|4α=↓|4u|β2|βn|βα+↓|β1x|g2|gn|gα+↓|g1|4α+↓|4u|β2|β
 1581  n|βα_↓|β1x|g2|gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x
 1581  ?|;{A3}|9|1|≡2|≡.|9|4[M|*/Pc|\] |πInstead of computing 
 1586  |εu(x|4α+↓|4x|β0) |πby steps H1, H2 as in the 
 1594  text, discuss the application of Horner's rule 
 1601  (2) when |εpolynomial |πmultiplication and addition 
 1607  are used instead of arithmetic in the domain 
 1615  of coe∃cients.|'{A3}|9|1|≡3|≡.|9|4|ε[|*/Pc|\] 
 1618  |πGive a method analogous to Horner's rule, for 
 1626  evaluating a polynomial in two variables |ε|¬K|βi|βα+↓|βj|β|
 1632  ¬E|βn|4u|βi|βjx|giy|gj. |π(This polynomial has 
 1636  |ε(n|4α+↓|41)(n|4α+↓|42)/2 |πcoe∃cients, and 
 1639  ``total degree'' |εn.) |πCount the number of 
 1646  additions and multiplications you use.|'{A3}|9|1|≡4|≡.|9|4|ε
 1651  [M|*/Pc|\] |πThe text shows that scheme (3) is 
 1659  superior to Horner's rule when we are evaluating 
 1667  a polynomial with real coe∃cients at a complex 
 1675  point |εz. |πCompare (3) to Horner's rule when 
 1683  |εboth |πthe coe∃cients and the variable |εz 
 1690  |πare complex numbers; how many (real) multiplications 
 1697  and addition-subtractions are required by each 
 1703  method?|'{A3}|9|1|≡5|≡.|9|4[|εM|*/|↔P|↔c|\] |πCount 
 1706  the number of multiplications and additions required 
 1713  by the second-order rule (4).|'|Hβ*?{U0}{H10L12M29}58320#Comp
folio 629 galley 3
 1718  iter Programming!(A.-W./Knuth)!ch. 4!f. 629!g. 
 1722  3D|'{H9L11M29}|9|1|≡6|≡.|9|4[|ε|*/|↔P|↔P|\] |π(L. 
 1725  de Jong and J. van Leeuwen.) Show how to improve 
 1735  on steps S1,|4.|4.|4.|4,|4S4 by computing only 
 1741  about |f1|d32|)|εn |πpowers of |εx.|'{A3}|9|1|≡7|≡.|9|4[M|*/|
 1746  ↔P|↔M|\] |πHow can |ε|≤b|β0,|4.|4.|4.|4,|4|≤b|βn 
 1750  |πbe calculated so that (6) has the value |εu(x|β0|4α+↓|4kh)
 1758   |πfor all |εk;|'{A3}|9|1|≡8|≡.|9|4[M|*/|↔P|↔c|\] 
 1763  |πThe factorial power |εx|gk |πis de_ned to be 
 1771  |εk*3(|fx|d5k|))|4α=↓|4x(x|4α_↓|41)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4
 1771  k|4α+↓|41). |πExplain how to evaluate |εu|βnx|gn|4α+↓|1|1|¬O
 1776  |4|¬O|4|¬O|1|1α+↓|4u|β1x|g1|4α+↓|4u|β0 |πwith 
 1778  at most |εn |πmultiplications and |ε2n|4α_↓|41 
 1784  |πadditions, starting with |εx |πand the |εn|4α+↓|43 
 1791  |πconstants |εu|βn,|4.|4.|4.|4,|4u|β0, 1, n|4α_↓|41.|'
 1795  {A3}|9|1|≡9|≡.|9|4[|εM|*/|↔P|↔M|\] |π(H. J. Ryser.) 
 1799  Show that if |εX|4α=↓|4(x|βi|βj) |πis an |εn|4α⊗↓|4n 
 1806  |πmatrix, then|'{A6}per(|εX)|4α=↓|4|↔k|4(|→α_↓1)|urnα_↓|≤e|β
 1808  1α_↓|4|¬O|4|¬O|4|¬O|4α_↓|≤e|βn|)|)|≥u|uc|)1|¬Ei|¬En|)|4|↔k|u
 1808  c|)1|¬Ej|¬En|)|4|≤e|βjx|βi|βj|;{A6}|πsummed over 
 1811  all |ε2|gn |πchoices of |ε|≤e|β1,|4.|4.|4.|4,|4|≤e|βn 
 1816  |πequal to 0 or 1 independently. count the number 
 1825  of addition and multiplication operations required 
 1831  to evaluate per |ε(X) |πby this formula.|'{A3}|≡1|≡0|≡.|9|4[
 1838  |εM|*/|↔P|↔O|\] |πThe permanent of an |εn|4α⊗↓|4n 
 1844  |πmatrix |εX|4α=↓|4(x|βi|βj) |πmay be calculated 
 1849  as follows: Start with the |εn |πquantities |εx|β1|β1, 
 1857  x|β1|β2,|4.|4.|4.|4,|4x|β1|βn. |πFor |ε1|4|¬E|4k|4|¬W|4n, 
 1860  |πassume that the (|ε|fn|d5k|)) |πquantities 
 1865  |εA|βk|βS |πhave been computed, for all |εk-|πelement 
 1872  subsets |εS |πof |ε|¬T1,|42,|4.|4.|4.|4,|4n|¬Y, 
 1876  |πwhere |εA|βk|βS|4α=↓|4|¬K|4x|β1|βj|m1|4.|4.|4.|4x|βk|βj|mk
 1877   |πsummed over all |εk*3 |πpermutations |εj|β1|4.|4.|4.|4j|βk
 1883   |πof the elements of |εS; |πthen form all of 
 1893  the sums|'{A6}|εA|β(|βk|βα+↓|β1|β)|βS|4α=↓|4|↔k|uc|)j|¬AS|)|
 1895  4A|βk|β(|βS|βα_↓|β|¬T|βj|β|¬Y|β)x|β(|βk|βα+↓|β1|β)|βj.|;
 1896  {A6}|πWe have per(|εX)|4α=↓|4A|βn|β|¬T|β1|β,|4|β.|4|β.|4|β.|
 1898  4|β,|4|βn|β|¬Y.|'|π!!|1|1How many additions and 
 1903  multiplications does this method require? How 
 1909  much temporary storage is needed?|'{A3}|≡1|≡1|≡.|9|4[|εM|*/|↔
 1914  C|↔c|\] |πIs there any way to evaluate the permanent 
 1923  of a general |εn|4α⊗↓|4n |πmatrix using a number 
 1931  of operations which does not grow exponentially 
 1938  with |εn?|'{A3}|≡1|≡2|≡.|9|4[M|*/|↔C|↔c|\] |πWhat 
 1942  is the minimum number of multiplications required 
 1949  to multiply two |εn|4α⊗↓|4n |πmatrices? Can the 
 1956  total number of operations be reduced to less 
 1964  than |εO(n|π|gl|gg|4|g7)?|'{A3}|≡1|≡3|≡.|9|4[|εM|*/|↔P|↔L|\] 
 1967  |πFind the inverse of the general _nite Fourier 
 1975  transform (37), by expressing |εF(t|β1,|4.|4.|4.|4,|4t|βn) 
 1980  |πin terms of the values of |εf|1(s|β1,|4.|4.|4.|4,|4s|βn). 
 1987  [Hint|*/:|\ |πSee Eq. 1.2.9<13.]|'{A3}|≡1|≡4|≡.|9|4[|εHM|*/|↔P
 1991  |↔l|\] |π(a) (|ε``Fast Fourier transforms.'') 
 1996  |πShow that the scheme (40) can be used to evaluate 
 2006  the one-dimensional fourier transform|'{A6}|εf|1(s)|4α=↓|4|↔
 2010  k|uc|)0|¬Et|¬W2|gn|)|4F(t)|≤v|gs|gt,!!|≤v|4α=↓|4e|ur2|≤pi/2|
 2010  gn|)|),!!0|4|¬E|4s|4|¬W|42|gn,|;{A6}|πusing arithmetic 
 2013  on complex numbers. (b) Apply this result to 
 2021  prove that we can obtain the coe∃cients of the 
 2030  product of two given polynomials, |εu(z)v(z), 
 2036  |πin |εO(n|4|πlog|4|εn) |πoperations of (exact) 
 2041  addition and multiplication of complex numbers, 
 2047  if |εu(z) |πand |εv(z) |πare |εn|πth degree polynomials 
 2055  with complex coe∃cients. [|εHint|*/: |\|πconsider 
 2060  the product of fourier transforms of the coe∃cients.]|'
 2068  {A3}|≡1|≡5|≡.|9|4[|εHM|*/|↔P|↔l|\] |πThe |εn|πth 
 2071  |εdivided di∩erence f|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn) 
 2074  |πof a function |εf|1(x) |πat |εn|4α+↓|41 |πdistinct 
 2081  points |εx|β0,|4x|β1,|4.|4.|4.|4,|4x|βn |πis 
 2084  de_ned by the formula |εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|
 2088  4α=↓|4{H12}({H9}f|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1)|
 2088  4α_↓|4f|1(x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1,|4x|βn){H12}){H9}/
 2088  (x|β0|4α_↓|4x|βn), |πfor |εn|4|¬Q|40. |πThus 
 2092  |εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4|¬K|β0|β|¬E|βk|β
 2092  |¬E|βn|4f|1(x|βk)/|≤p|ur|)0|¬Ej|¬En,j|=|↔6α=↓k|)(x|βk|4α_↓|4
 2092  x|βj) |πis a symmetric function of its |εn|4α+↓|41 
 2100  |πarguments. (a) Prove that |εf|1(x|β0,|4.|4.|4.|4,|4x|βn)|4
 2104  α=↓|4f|g(|gn|g)(|≤u)/n*3, |πfor some |ε|≤u |πbetween 
 2109  min(|εx|β0,|4.|4.|4.|4,|4x|βn) |πand max(x|β0,|4.|4.|4.|4,|4
 2111  x|βn), |πif the |εn|πth derivative |εf|1|g(|gn|g)(x) 
 2117  |πexists and is continuous. [|εHint|*/: |\|πProve 
 2123  that|'{A6}|εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4|↔j|ur
 2124  1|)0|)dt|β1|↔j|urt|β1|)0|)dt|β2|4|¬O|4|¬O|4|¬O|4|↔j|urt|βn|β
 2124  α_↓|β1|)0|)dt|βnf|g(|gn|g){H12}({H10}x|β0(1|4α_↓|4t|β1)|4α+↓
 2124  |4x|β1(t|β1|4α_↓|4t|β2)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4x|βn|β
 2124  α_↓|β1(t|βn|βα_↓|β1|4α_↓|4t|βn)|4α+↓|4x|βn(t|βn|4α_↓|40){H12
 2124  }){H10}.|;{A6}|π(This formula also de_nes |εf|1(x|β0,|4x|β1,
 2129  |4.|4.|4.|4,|4x|βn) |πin a useful manner when 
 2135  the |εx|βj |πare not distinct.)] If |εy|βj|4α=↓|4f|1(x|βj), 
 2142  |πshow that |ε|≤a|βj|4α=↓|4f|1(x|β0,|4.|4.|4.|4,|4x|βj) 
 2145  |πin Newton's interpolation polynomial (42).|'
 2150  {A3}|≡1|≡6|≡.|9|4[|εM|*/|↔P|↔P|\] |πHow can we 
 2154  readily compute the coe∃cients of |εu|g[|gn|g](x)|4α=↓|4u|βn
 2159  x|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β0, |πif 
 2161  we are given the values of |εx|β0, x|β1,|4.|4.|4.|4,|4x|βn|β
 2168  α_↓|β1, |≤a|β0, |≤a|β1,|4.|4.|4.|4,|4|≤a|βn |πin 
 2172  Newton's interpolation polynomial (15)?|'{A3}|≡1|≡7|≡.|9|4[|
 2176  εM|*/|↔M|↔o|\] |πIs there a way to evaluate the 
 2184  polynomial|'{A6}|ε|↔k|uc|)1|¬Ei|¬Wj|¬En|)|4x|βix|βj|4α=↓|4x|
 2185  β1x|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4x|βn|βα_↓|β1x|βn|;
 2186  {A6}|πwith fewer than |εn|4α_↓|41 |πmultiplications 
 2191  and |ε2n|4α_↓|44 |πadditions? (There are (|ε|fn|d52|)) 
 2197  |πterms.)|'{A3}|≡1|≡8|≡.|9|4[|εM|*/|↔P|↔c|\] |πIf 
 2200  the fourth-degree scheme (9) were changed to|'
 2207  {A6}|εy|4α=↓|4(x|4α+↓|4|≤a|β0)x|4α+↓|4|≤a|β1,!!u(x)|4α=↓|4{H
 2207  12}({H9}(y|4α_↓|4x|4α+↓|4|≤a|β2)y|4α+↓|4|≤a|β3{H12}){H9}|≤a|
 2207  β4,|;{A6}|πwhat formulas for computing the |ε|≤a|βj'|πs 
 2214  in terms of the |εu|βk'|πs would take the place 
 2223  of (10)?|'{A3}|≡1|≡9|≡.|9|4[|εM|*/|↔P|↔M|\] |πExplain 
 2227  how to determine the adapted coe∃cients |ε|≤a|β0, 
 2234  |≤a|β1,|4.|4.|4.|4,|4|≤a|β5 |πin (11) from the 
 2239  coe∃cients |εu|β5,|4.|4.|4.|4,|4u|β1, u|β0 |πof 
 2243  |εu(x) |πand _nd the |ε|≤a'|πs for the particular 
 2251  polynomial |εu(x)|4α=↓|4x|g5|4α+↓|45x|g4|4α_↓|410x|g3|4α_↓|4
 2252  50x|g2|4α+↓|413x|4α+↓|460.|'{A3}|≡2|≡0|≡.|9|4[|*/|↔P|↔O|\] 
 2254  |πWrite a |¬m|¬i|¬x program which evaluates a 
 2261  _fth-degree polynomial according to scheme (11); 
 2267  try to make the program as e∃cient as possible, 
 2276  by making slight modi_cations to (11). Use |¬m|¬i|¬x's 
 2284  ⊗oating-point arithmetic operators.|'{A3}|≡2|≡1|≡.|9|4[|*/|↔P
 2287  |↔c|\] |πFind two more ways to evaluate the polynomial 
 2296  |εx|g6|4α+↓|413x|g5|4α+↓|449x|g4|4α+↓|433x|g3|4α_↓|461x|g2|4
 2296  α_↓|437x|4α+↓|43 |πby scheme (12), using the 
 2302  two roots of (15) which were not considered in 
 2311  the text.|'{A3}|≡2|≡2|≡.|9|4[|ε|*/|↔O|↔l|\] |πWhat 
 2315  is the scheme for evaluating |εx|g6|4α_↓|43x|g5|4α+↓|4x|g4|4
 2320  α_↓|42x|g3|4α+↓|4x|g2|4α_↓|43x|4α_↓|41, |πusing 
 2322  Pan's method (16)?|'{A6}|≡2|≡3|≡.|9|4[|εHM|*/|↔L|↔c|\] 
 2326  |π(J. Eve.) Let |εf|1(z)|4α=↓|4a|βnz|gn|4α+↓|4a|βn|βα_↓|β1z|
 2329  gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|β0 
 2330  |πbe a polynomial of degree |εn |πwith real coe∃cients, 
 2339  having at least |εn|4α_↓|41 |πroots with a nonnegative 
 2347  real part. Let|'{A6}|h|εh(z)|4|∂α=↓|4a|βn|βα_↓|β1z|gn|gα_↓|g
 2350  1|4α+↓|4a|βn|βα_↓|β3z|gn|gα_↓|g2|4α+↓|1|1.|4.|4.|1|1α+↓|4a|β
 2350  (|βn|βα_↓|β1|β)|4|π|βm|βo|βd|4|β2|εz|gn|gα_↓|g1|g(|g)|g|πm|g
 2350  o|gd|4|g2.|4|E|n|;|ε| g(z)|4|Lα=↓|4a|βnz|gn|4α+↓|4a|βn|βα_↓|
 2351  β2z|gn|gα_↓|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|βn|4|π|βm|βo|
 2351  βd|4|β2|εz|gn|4|π|gm|go|gd|4|g2,>{A4}|ε| h(z)|4|Lα=↓|4a|βn|β
 2352  α_↓|β1z|gn|gα_↓|g1|4α+↓|4a|βn|βα_↓|β3z|gn|gα_↓|g3|4α+↓|1|1|¬
 2352  O|4|¬O|4|¬O|1|1α+↓|4a|β(|βn|βα_↓|β1|β)|4|π|βm|βo|βd|4|β2|εz|
 2352  g(|gn|gα_↓|g1|g)|4|π|gm|go|gd|4|g2.>{A6}Assume 
 2354  that |εh(z) |πis not identically zero.|'|Hβ{U0}{H10L12M29}58
folio 632 galley 4
 2360  320#Computer Programming!(A.-W./Knuth)!ch. 4!f. 
 2363  632!g. 4D|'{A12}{H9L11M29}!!|1|1a)|9|1Show that 
 2367  |εg(z) |πhas at least |εn|4α_↓|42 |πimaginary 
 2373  roots (i.e., roots whose real part is zero), 
 2381  and |εh(z) |πhas at least |εn|4α_↓|43 |πimaginary 
 2388  roots. [|εHint|*/: |\|πConsider the number of 
 2394  times the path |εf|1(z) |πcircles the origin 
 2401  as |εz |πgoes around the path shown in fig. 15, 
 2411  for a su∃ciently large radius |εR.]|'|π!!|1|1b)|9Prove 
 2418  that the squares of the roots of |εg(z)|4α=↓|40, 
 2426  h(z)|4α=↓|40 |πare all rea.|'{A3}|≡2|≡4|≡.|9|4[|εM|*/|≤P|≤M|\
 2430  ] |πFind values of |εc |πand |ε|≤a|βk, |≤b|βk 
 2438  |πsatisfying the conditions of Theorem|εu(x)|4α=↓|4(x|4α+↓|4
 2442  7)(x|g2|4α+↓|46x|4α+↓|410)(x|g2|4α+↓|44x|4α+↓|45)(x|4α+↓|41)
 2442  . |πChoose these values so that |ε|≤b|β2|4α=↓|40. 
 2449  |πGive two di=erent solutions to this problem*3|'
 2456  {A3}|≡2|≡5|≡.|9|4[|εM|*/|↔P|↔c|\] |πWhen the construction 
 2460  in the proof of Theorem M is applied to the (ine∃cient) 
 2471  polynomial chain|'{A6}|ε|≤l|β1|4|∂α=↓|4|≤a|β1|4α+↓|4|≤l|β0,!
 2473  !|≤l|β2|4|∂α=↓|4|→α_↓|≤l|β0|4α_↓|4|≤l|β0,!!|≤l|β3|4|∂α=↓|4|≤
 2473  l|β1|4α+↓|4|≤l|β1,!!|≤l|β4|4|∂α=↓|4|≤a|β2|4α⊗↓|4|≤l|β3,|;
 2474  {A3}| |≤l|β5|4|Lα=↓|4|≤l|β0|4α_↓|4|≤l|β0,| |≤l|β6|4|Lα=↓|4|≤
 2474  a|β6|4α_↓|4|≤l|β5,| |≤l|β7|4|Lα=↓|4|≤a|β7|4α+↓|4|≤l|β6,| |≤l
 2474  |β8|4|Lα=↓|4|≤l|≤l|β7|4α⊗↓|4|≤l|β7,>{A3}|πhow 
 2476  can |ε|≤b|β1, |≤b|β2,|4.|4.|4.|4,|4|≤b|β9 |πbe 
 2480  expressed in terms of |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|β8?|'
 2485  {A3}|≡2|≡6|≡.|9|4[M|*/|↔P|↔O|\] |π(a) Give the 
 2489  polynomial chain corresponding to Horner's rule 
 2495  for evaluating polynomials of degree |εn|4α=↓|43. 
 2501  |π(b) Using the construction in the proof of 
 2509  Theorem A, express |ε|≤k|β1, |≤k|β2, |≤k|β3, 
 2515  |πand the result polynomial |εu(x) |πin terms 
 2522  of |ε|≤b|β1, |≤b|β2, |≤b|β3, |≤b|β4, |πand |εx. 
 2529  |π(c) Show that the result set obtained in (b), 
 2538  as |ε|≤b|β1, |≤b|β2, |≤b|β3, |≤b|β4 |πindependently 
 2544  assume all real values, omits certain vectors 
 2551  in the result set of (a).|'{A3}|≡2|≡7|≡.|9|4|ε[M|*/|↔P|↔P|\] 
 2558  |πLet |εR |πbe a set which includes all |ε(n|4α+↓|41)-|πtupl
 2566  es |ε(q|βn,|4.|4.|4.|4,|4q|β1,|4q|β0) |πof real 
 2570  numbers such that |εq|βn|4|=|↔6α=↓|40; |πprove 
 2575  that |εR |πdoes not have at most |εn |πdegrees 
 2584  of freedom.|'{A3}|≡2|≡8|≡.|9|4[|εHM|*/|↔P|↔c|\] 
 2587  |πShow that if |εf|β0(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.
 2590  |4,|4f|βs(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs) |πare 
 2592  multivariate polynomials with integer coe∃cients, 
 2597  then there is a nonzero polynomial |εg(x|β0,|4.|4.|4.|4,|4x|
 2603  βs) |πwith integer coe∃cients wuch that |εg{H12}({H9}f|β0(|≤
 2609  a|β1,|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.|4
 2609  ,|4f|βs(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs){H12}){H9}|4α=↓|40 
 2610  |πfor all real |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|βs. 
 2614  (|πHence any polynomials chain with |εs |πparameters 
 2621  has at most |εs |πdegrees of freedom.) [|εHint|*/: 
 2629  |\|πUse the theorems about ``algebraic dependence'' 
 2635  which are found, for example, in B. L. van der 
 2645  Waerden's |εModern Algebra, |πtr. by Fred Blum 
 2652  (New York: Ungar, 1949), Section 64.]|'{A3}|≡2|≡9|≡.|9|4[|εM
 2658  |*/|↔P|↔c] |\|πLet |εR|β1, R|β2,|4.|4.|4.|4,|4R|βm 
 2662  |πall be sets of |ε(n|4α+↓|41)-|πtuples of real 
 2669  numbers having at most |εt |πdegrees of freedom. 
 2677  Show that the union |εR|β1|4|↔q|4R|β2|4|↔q|4|¬O|4|¬O|4|¬O|4|
 2681  ↔q|4R|βm |πalso has at most |εt |πdegrees of 
 2689  freedom.|'{H9L11M29}{A3}|≡3|≡0|≡.|9|4[|εM|*/|↔P|↔l|\] 
 2691  |πProve that a polynomial chain with |εm|β1 |πchain 
 2699  multiplications and |εm|β2 |πparameter multiplications 
 2704  has at most |ε2m|β1|4α+↓|4m|β2|4α+↓|4|≤d|β0|βm|m1 
 2708  |πdegrees of freedom. [|εHint|*/: |\|πGeneralize 
 2713  Theorem M, showing that the _rst chain multiplication 
 2721  and each parameter multiplication can essentially 
 2727  introduce only one new parameter into the result 
 2735  set.]|'{A3}|≡3|≡1|≡.|9|4[|εM|*/|↔P|↔L|\] |πProve 
 2738  that a polynomial chain capable of computing 
 2745  all |εmonic |πpolynomials of degree |εn |πhas 
 2752  at least |"l|εn/2|"L |πmultiplications and at 
 2758  least |εn |πaddition-subtractions.|'{A3}|≡3|≡2|≡.|9|4[|εM|*/|
 2761  ↔P|↔M|\] |πFind a polynomial chain of minimum 
 2768  possible length which can compute all polynomials 
 2775  of the form |εu|β4x|g4|4α+↓|4u|β2x|g2|4α+↓|4u|β0; 
 2779  |πprove that its length is minimal.|'{A3}|π|≡3|≡3|≡.|9|4[|εM
 2785  |*/|↔P|↔C|\] |πLet |εn|4|¬R|43 |πbe odd. Prove 
 2791  that a polynomial chain with |ε|"ln/2|"L|4α+↓|41 
 2797  |πmultiplication steps cannot compute all polynomials 
 2803  of degree |εn |πunless it has at least |εn|4α+↓|42 
 2812  |πaddition-subtraction steps. |ε[Hint|*/: |\|πSee 
 2816  exercise 30.]|'{A3}|≡3|≡4|≡.|9|4[|εM|*/|↔P|↔o|\] 
 2819  |πLet |ε|≤l|β0,|4|≤l|β1,|4.|4.|4.|4,|4|≤l|βr 
 2821  |πbe a polynomial chain in which all addition 
 2829  and subtraction steps are parameter steps, and 
 2836  which contains at least one parameter multiplication. 
 2843  Assume that this scheme has |εm |πmultiplications 
 2850  and |εk|4α=↓|4r|4α_↓|4m |πaddition-subtractions, 
 2853  and that the polynomial computed by the chain 
 2861  has maximum degree |εn. |πProve that all polynomials 
 2869  computable by this chain, for which the coe∃cient 
 2877  of |εx|gn |πis not zero, can be computed by another 
 2887  chain which has at most |εm |πmultiplications 
 2894  and at most |εk |πadditions, and no subtractions; 
 2902  and whose last step is the only paramter multiplication.|'
 2911  {A3}|≡3|≡5|≡.|9|4[|εM|*/|↔P|↔C|\] |πShow that 
 2914  any polynomial chain which computes a general 
 2921  fourth degree polynomial using only three multiplications 
 2928  must have at least _ve addition-subtractions. 
 2934  |ε[Hint|*/: |\|πAssume that there are only four 
 2941  addition-subtractions, and show that exercise 
 2946  34 applies; this means the scheme must have a 
 2955  particular form which is incapable of representing 
 2962  all fourth degree polynomials.]|'{A3}|≡3|≡6|≡.|9|4[|εM|*/|↔P|
 2966  ↔p|\] |πShow that any polynomial chain which 
 2973  computes a general sixth-degree polynomial using 
 2979  only four multiplications must have at least 
 2986  seven addition-subtractions. (Cf. exercise 35.)|'
 2991  {A3}|≡3|≡7|≡.|9|4[|εM|*/|↔P|↔O|\] |π(T. S. Motzkin.) 
 2995  Show that ``almost all'' rational functions of 
 3002  the form|'{A6}|ε(u|βnx|gn|4α+↓|4u|βn|βα_↓|β1x|gn|gα_↓|g1|4α+
 3004  ↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x|4α+↓|4u|β0)/(x|gn|4α+↓|4v|β
 3004  n|βα_↓|β1x|gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4v|β1x|4α
 3004  +↓|4v|β0),|;{A4}|πwith coe∃cients in a _eld |εS, 
 3011  |πcan be evaluated using the scheme|'{A6}|ε|≤a|β1|4α+↓|4|≤b|
 3017  β1/{H12}({H9}x|4α+↓|4|≤a|β2|4α+↓|4|≤b|β2/(x|4α+↓|1|1.|4.|4.|
 3017  4|≤b|βn/(x|4α+↓|4|≤a|βn|βα+↓|β1)|4|¬O|4|¬O|4|¬O){H12}){H9},|
 3017  ;{A6}|(fpr siotab_e |ε|≤a|βj, |≤b|βj |πin |εS. 
 3024  (|πThis continued fraction scheme has |εn |εdivisions 
 3031  and |ε2n |πadditions; by ``almost all'' rational 
 3038  functions we mean all except those whose coe∃cients 
 3046  satisfy some nontrivial polynomial equation.) 
 3051  Determine the |ε|≤a'|πs and |ε|≤b'|πs for the 
 3058  rational function |ε(x|g2|4α+↓|410x|4α+↓|429)/(x|g2|4α+↓|48x
 3060  |4α+↓|419).|'{A3}|≡3|≡8|≡.|9|4[HM|*/|↔L|↔P|\] 
 3062  |π(A. M. Garsia, 1962.) The purpose of this exercise 
 3071  is to prove that Horner's rule is really optimal 
 3080  if no preliminary adaptation of coe∃cients is 
 3087  made; we need |εn |πmultiplications and |εn |πadditions 
 3095  to compute |εu|βnx|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x|4α
 3097  +↓|4u|β0, |πif the variables |εu|βn,|4.|4.|4.|4,|4u|β1, 
 3102  u|β0, x, |πand arbitrary constants are given. 
 3109  consider chains which are as before except that 
 3117  |εu|βn,|4.|4.|4.|4,|4u|β1, u|β0, x |πare each 
 3122  considered to be variables; we may say, for example, 
 3131  that |ε|≤l|βα_↓|βj|βα_↓|β1|4α=↓|4u|βj, |≤l|β0|4α=↓|4x. 
 3134  |πIn order to show that Horner's rule is best, 
 3143  it is convenient to prove a somewhat more general 
 3152  theorem: Let |εA|4α=↓|4|ε(a|βi|βj), 0|4|¬E|4i|4|¬E|4m, 
 3156  0|4|¬E|4j|4|¬E|4n, |πbe an |ε(m|4α+↓|41)|4α⊗↓|4(n|4α+↓|41) 
 3160  |πmatrix of real numbers, of rank |εn|4α+↓|41; 
 3167  |πand let |εB|4α=↓|4(b|β0,|4.|4.|4.|4,|4b|βm) 
 3170  |πbe a vector of real numbers. Prove that |εany 
 3179  polynomial chain which computes|'{A6}P(x;|4u|β0,|4.|4.|4.|4,
 3183  |4u|βn)|4α=↓|4|↔k|uc|)0|¬Ei|¬Em|)(a|βi|β0u|β0|4α+↓|1|1|¬O|4|
 3183  ¬O|4|¬O|1|1α+↓|4a|βi|βnu|βn|4α+↓|4b|βi)x|gi|;
 3184  {A6}involves at least n chain multiplications. 
 3190  |π(Note that this does not mean only that we 
 3199  are considering some _xed chain in which the 
 3207  parameters |ε|≤a|βj |πare assigned values depending 
 3213  on |εA |πand |εB; |πit means that both the chain 
 3223  |εand |πthe values of the |ε|≤a'|πs may depend 
 3231  on the given matrix |εA |πand vector |εB. |πNo 
 3240  matter how |εA, B, |πand the values of |ε|≤a|βj 
 3249  |πare chosen, it is impossible to compute |εP(x;|4u|β0,|4.|4
 3256  .|4.|4,|4u|βn) |πwithout doing |εn ``|πchainstep'' 
 3261  multiplications.) The assumption that |εA |πhas 
 3267  rank |εn|4α+↓|41 |πimplies that |εm|4|¬R|4n. 
 3272  [Hint|*/: |\|πShow that from any such scheme we 
 3280  can derive another which has one less chain multiplication 
 3289  and which has |εn |πdecreased by one.]|'β*?*?{U0}{H10L12M29}58
folio 635 galley 5
 3296  320#Computer Programming!(A.-W./knuth)!ch. 4!f. 
 3299  g. 5D|'{A12}{H9L11M29}|≡3|≡9|≡.|9|4[M|*/|↔P|↔m|\] 
 3302  |π(T. S. Motzkin, 1954.) Show that schemes of 
 3310  the form |εw|β1|4α=↓|4x(x|4α+↓|4|≤a|β1)|4α+↓|4|≤b|β1, 
 3313  w|βk|4α=↓|4w|βk|βα_↓|β1(w|β1|4α+↓|4|≤g|βkx|4α+↓|4|≤a|βk)|4α+
 3313  ↓|4|≤d|βkx|4α+↓|4|≤b|βk |πfor |ε1|4|¬W|4k|4|¬E|4m, 
 3316  |πwhere the |ε|≤a|βk, |≤b|βk |πare real and the 
 3324  |ε|≤g|βk|≤d|βk |πare integers, can be used to 
 3331  evaluate all monic polynomials of degree 2|εm 
 3338  |πover the real numbers. (We may have to choose 
 3347  the |ε|≤g|βk |πand |ε|≤d|βk |πdi=erently for 
 3353  di=erent polynomials.) Try to let |ε|≤d|βk|4α=↓|40 
 3359  |πwhenever possible.|'*?*?*?*?{H9L11M29}{A3}|≡4|≡0|≡.|9|4[|εM|*/|
 3361  ↔M|↔O|\] |πCan the lower bound in the number 
 3369  of multiplications in Theorem C be raised from 
 3377  |ε|"ln/2|"L|4α+↓|41 |πto |ε|"pn/2|"P|4α+↓|41? 
 3380  |π(Cf. exercise 33. An unfounded remark that 
 3387  Belaga [|εDokladi Akad. Nauk SSSR |≡1|≡2|≡3 (1958), 
 3394  775<777] |πgave such an improvement has appeared 
 3401  several times in the literature.)|'{A3}|≡4|≡1|≡.|9|4[|ε|*/|↔P
 3406  |↔P|\] |π(Oscar Buneman.) Show that the real 
 3413  and imaginary parts of |ε(a|4α+↓|4bi)(c|4α+↓|4di) 
 3418  |πcan be obtained by doing 3 multiplications 
 3425  and 5 additions of real numbers.|'|≡4|≡2|≡.|9|4[|ε|*/|↔L|↔o|\
 3431  ] |π(M. Paterson and L. Stockmeyer.) (a) Prove 
 3439  that a polynomial chain with |εm|4α=↓|42 |πchain 
 3446  multiplications has at most |εm|g2|4α+↓|41 |πdegrees 
 3452  of freedom. (b) Show that for all |εn|4|¬R|42 
 3460  |πthere exist polynomials of degree |εn, |πall 
 3467  of whose coe∃cients are 0 or 1, which cannot 
 3476  be evaluated by any polynomial chain with lesss 
 3484  than |"l{U19}|εn|)|"L |πmultiplications, if we 
 3489  require all parameters |ε|≤a|βj |πto be integers. 
 3496  (c) Show that any polynomial of degree |εn |πwith 
 3505  integer coe∃cients can be evaluated by an all-integer 
 3513  algorithm which performs at most |ε2|"l{U19}n|)|"L 
 3519  |πmultiplications, if we don't care how many 
 3526  additions we do.|'{A3}|≡4|≡3|≡.|9|4[|*/|ε|↔P|↔P|\] 
 3530  |πExplain how to evaluate |εx|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+
 3534  ↓|4x|4α+↓|41 |πwith |ε2l(n|4α+↓|41)|4α_↓|42 |πmultiplication
 3537  s and |εl(n|4α+↓|41) |πadditions (no divisions 
 3543  or subtractions).|'{H10L12M29}{A24}|≤⊂|∨4|∨.|∨7|∨.|9|4|∨M|∨A
 3545  |∨N|∨I|∨P|∨U|∨L|∨A|∨T|∨I|∨O|∨N|9|1|∨O|∨F|9|1|∨P|∨O|∨W|∨E|∨R|
 3545  9|1|∨S|∨E|∨R|∨I|∨E|∨S|'{A12}If we are given two 
 3551  power series|'{A6}|εU(z)|4α=↓|4U|β0|4α+↓|4U|β1z|4α+↓|4U|β2z|
 3553  g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4,!!V(z)|4α=↓|4V|β0|4α+↓|4V|β1z|4α+
 3553  ↓|4V|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4,|J!(1)|;{A6}|πwhose 
 3555  coe∃cients belong to a _eld, we can form their 
 3564  sum, thier product, their quotient, etc., to 
 3571  obtain new power series. A polynomial is obviously 
 3579  a special case of a power series, in which there 
 3589  are only _nitely many terms.|'!|4|4|4|4Of course, 
 3596  only a _nite number of terms can be represennted 
 3605  and stored within a computer, so it makes sense 
 3614  to ask whether power series arithmetic is even 
 3622  possible on computers; and if it is possible, 
 3630  what makes it di=erent from polynomial arithmetic? 
 3637  The answer is that we work only with the _rst 
 3647  |εN |πcoe∃cients of the powerseries, where |εN 
 3654  |πis a parameter which may in principle be arbitrarily 
 3663  large; instead of ordinary polynomial arithmetic, 
 3669  we are essentially doing polynomial arithmetic 
 3675  modulo |εz|gN, |πand this often leads to a seomewhat 
 3684  di=erent point of view. Furthermore, special 
 3690  operations, like ``reversion,'' can be performed 
 3696  on power series but not on polynomials, since 
 3704  polynomials are not closed under these operations.|'
 3711  !|4|4|4|4Manipulation of power series has several 
 3717  applications to numerical analysis, but perhaps 
 3723  its greatest use is the determination of asymptotic 
 3731  expansions (as we have seen in Section 1.2.11.3), 
 3739  or the calculation of quantities de_ned by certain 
 3747  generating functions. The latter applications 
 3752  make it desirable to calculate the coe∃cients 
 3759  exactly, instead of with ⊗oating-point arithmetic. 
 3765  All of the algorithms in this section, with obvious 
 3774  exceptions, can be done using rational operations 
 3781  only, so the techniques of Section 4.5.1 can 
 3789  be used to obtain exact results when desired.|'
 3797  !|4|4|4|4The calculation of |εW(z)|4α=↓|4U(z)|4|¬N|4V(z) 
 3801  |πis, of course, trivial, since we have |εW|βn|4α=↓|4U|βn|4|
 3808  ¬N|4V|βn |πfor |εn|4α=↓|40, 1, 2,|4.|4.|4. |πIt 
 3814  is also easy to calculate |εW(z)|4α=↓|4U(z)V(z), 
 3820  |πusing the familiar ``Cauchy product rule'':|'
 3826  {A6}|εW|βn|4α=↓|4|↔k|uc|)0|¬Ek|¬En|)|4U|βkV|βn|βα_↓|βk|4α=↓|
 3826  4U|β0V|βn|4α+↓|4U|β1V|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+
 3826  ↓|4U|βnV|β0.|J!(2)|;{A6}|π!|4|4|4|4The quotient 
 3829  |εW(z)|4α=↓|4U(z)/V(z), |πwhen |εV|β0|4|=|↔6α=↓|40, 
 3832  |πcan be obtained by interchanging |εU |πand 
 3839  |εW |πin (2); we obtain the rule|'{A6}|h|εW|βn|4|∂α=↓|4(U|βn
 3846  |4α_↓|4W|β0V|βn|4α_↓|4W|β1V|βn|βα_↓|β1|4α_↓|1|1|¬O|4|¬O|4|¬O
 3846  |1|1α_↓|4W|βn|βα_↓|β1V|β1)/V|β0.|E|n|;| W|βn|4|Lα=↓|4|↔aU|βn
 3847  |4α_↓|4|↔k|uc|)0|¬Ek|¬Wn|)|4W|βkV|βn|βα_↓|βk|↔s|↔hV|β0>
 3848  {A4}|Lα=↓|4(U|βn|4α_↓|4W|β0V|βn|4α_↓|4W|β1V|βn|βα_↓|β1|4α_↓|
 3848  1|1|¬O|4|¬O|4|¬O|1|1α_↓|4W|βn|βα_↓|β1V|β1)/V|β0.|J!(3)>
 3849  {A6}|πThis recurrence relation for the |εW'|πs 
 3855  makes it easy to determine |εW|β0, W|β1, W|β2,|4.|4.|4. 
 3863  |πsuccessively, without inputting |εU|βn |πand 
 3868  |εV|βn |πuntil after |εW|βn|βα_↓|β1 |πhas been 
 3874  computed. Let us say that a power-series manipulation 
 3882  algorithm with the latter property is ``on-line''; 
 3889  an on-line algorithm can be used to determine 
 3897  |εN |πcoe∃cients |εW|β0, W|β1,|4.|4.|4.|4,|4W|βN|βα_↓|β1 
 3901  |πof the result without knowing |εN |πin advance, 
 3909  so it is possible in theory to run the algorithm 
 3919  inde_nitely and compute the entire power series; 
 3926  or to run it until a certain condition is met. 
 3936  (The opposite of ``on-line'' is ``o=-line.'')|'
 3942  !|4|4|4|4If the coe∃cients |εU|βk |πand |εV|βk 
 3948  |πare integers but the |εW|βk |πare not, recurrence 
 3956  (3) involves computation with fractions. This 
 3962  can be avoided by the all-integer approach described 
 3970  in exercise 2.|'!|4|4|4|4Let us now consider 
 3977  the operation of computing |εW(z)|4α=↓|4V(z)|g|≤a, 
 3982  |πwhere |ε|≤a |πis an ``arbitrary'' power. For 
 3989  example, we could calculate the square root of 
 3997  |εV(z) |πby taking |ε|≤a|4α=↓|4|f1|d32|), |πor 
 4002  we could _nd |εV(z)|gα_↓|g1|g0 |πor even |εV(z)|g|≤p. 
 4009  |πIf |εV|βm |πis the _rst nonzero coe∃cient of 
 4017  |εV(z), |πwe have|'{A6}{A7}(4)|E|?{B7}|εV(z)|4|∂α=↓|4V|βmz|g
 4021  m{H12}({H10}1|4α+↓|4(V|βm|βα+↓|β1/V|βm)z|4α+↓|4(V|βm|βα+↓|β2
 4021  /V|βm)z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O{H12}){H10},|;
 4022  {A4}| V(z)|g|≤a|4|Lα=↓|4V|ur|≤a|)m|)z|g|≤a|gm{H12}({H10}1|4α
 4022  +↓|4(V|βm|βα+↓|β1/V|βm)z|4α+↓|4(V|βm|βα+↓|β2/V|βm)z|g2|4α+↓|
 4022  1|1|¬O|4|¬O|4|¬O{H12}){H10}|g|≤a.>{A6}|πThis 
 4024  will be a power series if and only if |ε|≤am 
 4034  |πis a nonnegative integer. From (4) we can see 
 4043  that the problem of computing general powers 
 4050  can be reduced to the case that |εV|β0|4α=↓|41; 
 4058  |πthen the problem is to _nd coe∃cients of|'{A6}|εW(z)|4α=↓|
 4066  4(1|4α+↓|4V|β1z|4α+↓|4V|β2z|g2|4α+↓|4V|β3z|g3|4α+↓|1|1|¬O|4|
 4066  ¬O|4|¬O)|g|≤a.|J!(5)|;{A6}|πClearly |εW|β0|4α=↓|41|g|≤a|4α=↓
 4068  |41.|'|π!|4|4|4|4The obvious way to _nd the coe∃cients 
 4076  of (5) is to use the binomial theorem (Eq. 1.2.9<19), 
 4086  or (if |ε|≤a |πis a positive integer) to try 
 4095  repeated squaring as in Section 4.6.3, but a 
 4103  much simpler and more e∃cient device for calculating 
 4111  powers has been suggested by J. C. P. Miller. 
 4120  [See P. Henrici, |εJACM |≡3 (1956), 10<15.] |πIf 
 4128  |εW(z)|4α=↓|4V(z)|g|≤a, |πwe have by di=erentiation|'
 4133  {A6}|εW|β1|4α+↓|42W|β2z|4α+↓|43W|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬
 4133  O|1|1α=↓|4W|¬S(z)|4α=↓|4|≤aV(z)|g|≤a|gα_↓|g1V|¬S(z);|J!(6)|;
 4134  {A6}|πtherefore|'{A6}|εW|¬S(z)V(z)|4α=↓|4|≤aW(z)V|¬S(z).|J!(
 4135  7)|;{A6}|πIf we now equate the coe∃cients of 
 4143  |εz|gn|gα_↓|g1 |πin (7), we _nd that|'{A6}|ε|↔k|uc|)0|¬Ek|¬E
 4149  n|)kW|βkV|βn|βα_↓|βk|4α=↓|4|≤a|↔k|uc|)0|¬Ek|¬En|)|4(n|4α_↓|4
 4149  k)W|βkV|βn|βα_↓|βk,|J!(8)|;{A6}|πand this gives 
 4153  us a useful computational rule,|'{A6}|h|εW|βn|4|∂α=↓|4()|≤a|
 4158  4α+↓|41|4α_↓|4n)V|β1W|βn|βα_↓|β1|4α+↓|4(2(|≤a|4α+↓|41)|4α_↓|
 4158  4n)V|β2W|βn|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4n|≤aV|βn)/
 4158  n,!!n|4α+↓|41.|E|n|;| W|βn|4|Lα=↓|4|↔k|uc|)1|¬Ek|¬En|)|4|↔a|
 4159  ↔a|(|≤a|4α+↓|41|d2n|)|↔sk|4α_↓|41|↔sV|βkW|βn|βα_↓|βk>
 4160  {A4}|Lα=↓|4{H12}({H10}(|≤a|4α+↓|41|4α_↓|4n)V|β1W|βn|βα_↓|β1|
 4160  4α+↓|4(2(|≤a|4α+↓|41)|4α_↓|4n)V|β2W|βn|βα_↓|β2|4α+↓|1|1|¬O|4
 4160  |¬O|4|¬O|1|1α+↓|4n|≤aV|βn{H12}){H10}/n,!!n|4|¬R|41.>
 4161  {A2}(9)|?{A6}|H*?*?*?*?{U0}{H10L12M29}58320#Computer 
folio 638 galley 6
 4163  Programming!(A.-W./Knuth)!ch.!f. 638!g. 6D|'{A12}|π!|4|4|4|4
 4166  The transformation of power series which is perhaps 
 4174  of greatest interest is called ``reversion of 
 4181  series.'' This problem is to solve the equation|'
 4189  {A6}|εz|4α=↓|4t|4α+↓|4V|β2t|g2|4α+↓|4V|β3t|g3|4α+↓|4V|β4t|g4
 4189  |4α+↓|1|1|¬O|4|¬O|4|¬O|J!(10)|;{A6}|πfor |εt, 
 4192  |πobtaining the coe∃cients of the power series|'
 4199  {A6}|εt|4α=↓|4z|4α+↓|4W|β2z|g2|4α+↓|4W|β3z|g3|4α+↓|4W|β4z|g4
 4199  |4α+↓|1|1|¬O|4|¬O|4|¬O|4.|J!(11)|;{A6}|πSeveral 
 4201  interesting ways to achieve such a reversion 
 4208  are known; we might say that the ``classical'' 
 4216  method is one based on Lagrange's remarkable 
 4223  inversion formula [|εM|=1emoires Acad. royale 
 4228  des Sciences et Belles-Lettres de Berlin |≡2|≡4 
 4235  (1768), 251<326], |πwhich states that|'{A6}|εW|βn|4α=↓|4U|βn
 4240  |βα_↓|β1/n,|;|πif|'|εU|β0|4α+↓|4U|β1t|4α+↓|4U|β2t|g2|4α+↓|1|
 4242  1|¬O|4|¬O|4|¬O|1|1α=↓|4(1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|4α+↓|1|
 4242  1|¬O|4|¬O|4|¬O)|gα_↓|gn.|J!(12)|;{A6}|πFor example, 
 4245  we have (|ε1|4α_↓|4t)|gα_↓|g5|4α=↓|4(|f4|d54|))|4α+↓|4(|f5|d
 4247  54|))t|4α+↓|4(|f6|d54|))t|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4; 
 4248  |πhence |εW|β5 |πin the reversion of |εz|4α=↓|4t|4α_↓|4t|g2 
 4255  |πis equal to (|f8|d54|))/5|4α=↓|414. This checks 
 4261  with the formulas for enumerating binary trees 
 4268  in Section 2.3.4.4.|'!|4|4|4|4Relation (12) shows 
 4274  that we can revert the series (10) if we compute 
 4284  |ε(1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|
 4284  gn |πfor |εn|4α=↓|41, 2, 3,|4.|4.|4.|4. |πA straightforward 
 4291  application of this idea would lead to an oλ-line 
 4300  power-series algorithm which uses approximately 
 4305  |εN|g3/2 |πmultiplications to _nd |εN |πcoe∃cients, 
 4311  but Eq. (9) makes it possible to work with onl 
 4321  y the _rst |εn |πcoe∃cients of |ε(1|4α+↓|4V|β2t|4α+↓|4V|β3t|
 4327  g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn, |πobtaining 
 4329  an on-line algorithm which has only about |εN|g3/6 
 4337  |πmultiplications.|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m 
 4339  |≡L (|εLagrangian power-series reversion). |πThis 
 4344  on-line algorithm inputs the value of |εV|βn 
 4351  |πin (10) and outputs the value of |εW|βn |πin 
 4360  (11), for |εn|4α=↓|42, 3, 4,|4.|4.|4.|4,|4N. 
 4365  |π(The number |εN |πneed not be speci_ed in advance; 
 4374  some other termination condition may be substituted.)|'
 4381  {A6}{I1.8H}|≡L|≡1|≡.|9[Initialize.] Set |εn|4|¬L|41, 
 4384  U|β0|4|¬L|41. (|πDuring the course of this algorithm, 
 4391  we will have|'{A6}!!{H12}({H10}1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|
 4394  4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn|4α=↓|4U|β0|4α+↓|4U|β1t|4α+↓|1
 4394  |1|¬O|4|¬O|4|¬O|1|1α+↓|4U|βn|βα_↓|β1t|gn|gα_↓|g1|4α+↓|4O(t|g
 4394  n).{H12}){H10}|;{A3}(13)|?{A6}|π|≡L|≡2|≡.|9[Input 
 4397  |εV|βn.] |πIncrease |εn |πby 1. If |εn|4|¬Q|4N, 
 4404  |πthe algorithm terminates; otherwise input the 
 4410  next coe∃cient, |εV|βn.|'{A3}|≡L|≡3|≡.|9[|πdivide.] 
 4414  Set |εU|βk|4|¬L|4U|βk|4α_↓|4U|βk|βα_↓|β1V|β2|4α_↓|1|1|¬O|4|¬
 4415  O|4|¬O|1|1α_↓|4U|β1V|βk|4α_↓|4V|βk|βα+↓|β1, |πfor 
 4417  |εk|4α=↓|41, 2,|4.|4.|4.|4,|4n|4α_↓|42 (|πin 
 4420  this order); then set|'{A6}!!|εU|βn|βα_↓|β1|4|¬L|4|→α_↓2U|βn
 4424  |βα_↓|β2V|β2|4α_↓|43U|βn|βα_↓|β3V|β3|4α_↓|1|1|¬O|4|¬O|4|¬O|1
 4424  |1α_↓|4(n|4α_↓|41)U|β1V|βn|βα_↓|β1|4α_↓|4nV|βn|βα_↓|β1.|;
 4425  {A6}!!|π{H12}({H10}We have thereby divided |εU(z) 
 4430  |πby |εV(z)/z; |πcf. (3) and (9).{H12})|'{H10}{A3}|≡L|≡4|≡.|
 4436  9[Output |εW|βn.] |πOutput |εU|βn|βα_↓|β1/n (|πwhich 
 4441  is |εW|βn) |πand return to L2.|'{IC}{H9}|≡F|≡i|≡g|≡. 
 4448  |≡1|≡6|≡.|9|4Power-series reversion by algorithm 
 4452  L.|;{A6}{H10}When applied to the example |εz|4α=↓|4t|4α_↓|4t
 4458  |g2, |πthe computation in Algorithm L is|'|∂!!!|∂!!!|∂!!!|∂!
 4465  !∂!|∂!!!|∂!!!|∂!!!|∂!!!|∂|E|;|>|εn|;V|βn|;U|β0|;
 4470  U|β1|;U|β2|;U|β3|;U|β4|;W|βn|;>{A2}|>1|;1|;1|;
 4480  |;|;|;|;|9|11|;>|>2|;|→α_↓1|4|4|4|4|;1|;1|;|;
 4492  |;|;1|;>|>3|;0|;1|;3|;|9|16|;|;|;|9|12|;>|>4|;
 4508  0|;1|;4|;10|;20|;|;|9|15|;>|>5|;0|;1|;5|;15|;
 4522  35|;70|;14|;>{A6}|πExercise 8 shows a slight 
 4531  modi_cation of algorithm L will solve a considerably 
 4539  more general problem with only a little more 
 4547  e=ort.|'!|4|4|4|4Let us now consider solving 
 4553  the equation|'{A6}|εU|β1z|4α+↓|4U|β2z|g2|4α+↓|4U|β3z|g3|4α+↓
 4555  |1|1|¬O|4|¬O|4|¬O|1|1α=↓|4t|4α+↓|4V|β2t|g2|4α+↓|4V|β3t|g3|4α
 4555  +↓|1|1|¬O|4|¬O|4|¬O|J!(14)|;{A6}|πfor |εt, |πobtaining 
 4559  the coe∃cients of the power series|'{A6}|εt|4α=↓|4W|β1z|4α+↓
 4565  |4W|β2z|g2|4α+↓|4W|β3z|g3|4α+↓|4W|β4z|g4|4α+↓|1|1|¬O|4|¬O|4|
 4565  ¬O|4.|J!(15)|;{A6}Eq. (10) is the special case 
 4572  |εU|β1|4α=↓|41, U|β2|4α=↓|4U|β3|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓
 4573  |40. |πIf |εU|β1|4|=|↔6α=↓|40, |πwe may assume 
 4579  that |εU|β1|4α=↓|41, |πif we replace |εz |πby 
 4586  |ε(U|β1z); |πbut we shall consider the general 
 4593  equation (14), since |εU|β1 |πmight equal zero.|'
 4600  {A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡m |≡T (|εGeneral 
 4603  power-series reversion). |πThis on-line algorithm 
 4608  inputs the values of |εU|βn |πand |εV|βn |πin 
 4616  (14) and outputs the value of |εW|βn |πin (15), 
 4625  for |εn|4α=↓|41, 2, 3,|4.|4.|4.|4,|4N. |πAn auxiliary 
 4631  matrix |εT|βm|βn, 1|4|¬E|4m|4|¬E|4n|4|¬E|4N, 
 4634  |πis used in the calculations.|'{A6}{I1.8H}|≡T|≡1|≡.|9[Initi
 4639  alize.] Set |εn|4|¬L|41. |πLet the _rst two inputs 
 4647  (namely, |εU|β1 |πand |εV|β1) |πbe stored in 
 4654  |εT|β1|β1 |πand |εV|β1, |πrespectively. (We must 
 4660  have |εV|β1|4α=↓|41).|'{A3}|π|≡T|≡2|≡.|9[Output 
 4663  |εW|βn.] |πOutput the value of |εT|β1|βn (|πwhich 
 4670  is |εW|βn).|'|π|≡T|≡3|≡.|9[Input |εU|βn, V|βn.] 
 4675  |πIncrease |εn |πby 1. If |εn|4|¬Q|4N, |πthe 
 4682  algorithm terminates; otherwise store the next 
 4688  two inputs (namely |εU|βn |πand |εV|βn) |πin 
 4695  |εT|β1|βn |πand |εV|βn, |πrespectively.|'{A3}|≡T|≡4|≡.|9[Mul
 4699  tiply.] Set|'{A6}!!|εT|βm|βn|4|¬L|4T|β1|β1T|βm|βα_↓|β1|β,|βn
 4701  |βα_↓|β1|4α+↓|4T|β1|β2T|βm|βα_↓|β1|β,|βn|βα_↓|β2|4α+↓|1|1|¬O
 4701  |4|¬O|4|¬O|1|1α+↓|4T|β1|β,|βn|βα_↓|βm|βα+↓|β1T|βm|βα_↓|β1|β,
 4701  |βm|βα_↓|β1|;{A6}!!|πand |εT|β1|βn|4|¬L|4T|β1|βn|4α_↓|4V|βmT
 4703  |βm|βn, |πfor |ε2|4|¬E|4m|4|¬E|4n. |π(After this 
 4708  step we have the conditions|'{A6}|εt|gm|4α=↓|4T|βm|βmz|gm|4α
 4713  +↓|4T|βm|β,|βm|βα+↓|β1z|gm|gα+↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1
 4713  α+↓|4T|βm|βnz|gn|4α+↓|4O(z|gn|gα+↓|g1),!!1|4|¬E|4m|4|¬E|4n.|
 4713  ;{A2}(16)|?{A6}|π!!It is easy to verify (16) 
 4721  by induction for |εm|4|¬R|42, |πand when |εm|4α=↓|41, 
 4728  |πwe have |εU|βn|4α=↓|4T|β1|βn|4α+↓|4V|β2T|β2|βn|4α+↓|1|1|¬O
 4730  |4|¬O|4|¬O|1|1α+↓|4V|βnT|βn|βn |πby (14) and 
 4734  (19).) Return to step T2.|'{IC}{A12}!|4|4|4|4Equation 
 4740  (16) explains the mechanism of this algorithm, 
 4747  which is due to Henry C. Thacher, Jr. [|εCACM 
 4756  |≡9 (1966), 10<11]. |πThe running time is essentially 
 4764  the same as Algorithm L, but considerably more 
 4772  storage space is required. An example of this 
folio 643 galley 7
 4780  algorithm is worked in exercise 9.|'|H*?*?*?{U0}{H10L12M29}5832
 4786  0#Computer Programming!(A.-W./Knuth)!ch. 4!f. 
 4789  643!g. 7D|'{A12}!|4|4|4|4Still another approach 
 4794  to power series reversion has been proposed by 
 4802  R. P. Brent and H. T. Kung [|εAnalytic computational 
 4811  complexity, |πed. by Traub (New York: Academic 
 4818  Press, 1975), 000<000], who observed that standard 
 4825  iterative procedures used to _nd roots of equations 
 4833  over the real numbers can usefully be applied 
 4841  also to equations over power series. In particular, 
 4849  consider Newton's method for computing approximations 
 4855  to a real number |εt |πsuch that |εf|1(t)|4α=↓|40, 
 4863  |πgiven a function |εf |πthat is well-behaved 
 4870  near |εt: |πIf |εx |πis a good approximation 
 4878  to |εT, |πthen |ε|≤f(x)|4α=↓|4x|4α_↓|4f|1(x)/f|¬S(x) 
 4882  |πwill be even better, for it we write |εx|4α=↓|4t|4α+↓|4|≤o
 4890   |πwe have |εf|1(x)|4α=↓|4f|1(t)|4α+↓|4|≤of|¬S(t)|4α+↓|4O(|≤
 4893  o|g2), f|¬S(x)|4α=↓|4f|¬S(t)|4α+↓|4O(|≤o), |πand 
 4896  |ε|≤'(x)|4α=↓|4t|4α+↓|4|≤o|4α_↓|4{H12}({H10}0|4α+↓|4|≤of|¬S(
 4896  t)|4α+↓|4O(|≤o|g2){H12}){H10}/{H12}({H10}f|¬S(t)|4α+↓|4O(|≤o
 4896  ){H12}){H10}|4α=↓|4t|4α+↓|4O(|≤o|g2). |πApplying 
 4898  this idea to power series, let |εf|1(x)|4α=↓|4V(x)|4α_↓|4U(z
 4904  ), |πwhere |εU |πand |εV |πare the pwer series 
 4913  in Eq. (14). We wish to lnd the power series 
 4923  |εt |πin |εz |πsuch that |εf|1(t)|4α=↓|40. |πLet 
 4930  |εx|4α=↓|4W|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|4|4α+↓|4W|βn|βα_↓|β1z|
 4930  gn|gα_↓|g1|4α=↓|4t|4α+↓|4O(z|gn) |πbe an ``approximation'' 
 4934  to |εt |πof order |εn; |πthen |ε|≤'(x)|4α=↓|4x|4α_↓|4f|1(x)/
 4940  f|¬S(x) |πwill be an approximation of order |ε2n, 
 4948  |πsince the assumptions of Newton's method hold 
 4955  for this |εf |πand |εt.|'!|4|4|4|4|πWe therefore 
 4962  can use the following procedure:|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t
 4967  |≡h|≡m |≡N |ε(General power series reversion 
 4973  by Newton's method).|9|4|πThis ``semi-on-line`` 
 4977  algorithm inputs the values of |εU|βn |πand |εV|βn 
 4985  in (14) |πfor |ε2|gk|4|¬E|4n|4|¬Q|42|gk|gα+↓|g1 
 4989  |πand then outputs the values of |εW|βn |πin 
 4997  (15) for |ε2|gk|4|¬E|4n|4|¬Q|42|gk|gα+↓|g1, |πthereby 
 5001  producing its answers in batches of |ε2|gk |πat 
 5009  a time, for |εk|4α=↓|40, 1, 2,|4.|4.|4.|4,|4K.|'
 5015  {A6}{I1.8H}|π|≡N|≡1|≡.|9[Initialize.] Set |εN|4|¬L|41. 
 5018  (|πWe will have |εN|4α=↓|42|gk.) |πInput the 
 5024  _rst coe∃cients |εU|β1 |πand |εV|β1 |π(where 
 5030  |εV|β1|4α=↓|41), |πand set |εW|β1|4|¬L|4U|β1.|'
 5034  {A3}|π|≡N|≡2|≡.|9[Output.] Output |εW|βn |πfor 
 5038  |εN|4|¬E|4n|4|¬Q|42N.|'{A3}|π|≡N|≡3|≡.|9[Input.] 
 5040  Set |εN|4|¬L|42N. |πIf |εN|4|¬Q|42|gK, |πthe 
 5045  algorithm terminates; otherwise input the values 
 5051  |εU|βn |πand |εV|βn |πfor |εN|4|¬E|4n|4|¬W|42N.|'
 5056  {A3}|π|≡N|≡4|≡.|9[Newtonian step.] Use an algorithm 
 5061  for power series composition (see exercise 11) 
 5068  to evaluate the coe∃cients |εQ|βj, R|βj (0|4|¬E|4j|4|¬W|4N) 
 5075  |πin the power series|'{A6}|h|εV|¬S(W|β1z|4α+↓|1|1|¬O|4|¬O|4
 5079  |¬O|1|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|4|∂α=↓|4Q|β0|4α+↓|4Q|β
 5079  1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g1|4α
 5079  +↓|4O(z|gN),|E|n|;!!U|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4U|β2
 5080  |βN|βα_↓|β1z|g2|gN|gα_↓|g1|4α_↓|4V(W|β1z|4α+↓|1|1|¬O|4|¬O|4|
 5080  ¬O|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|'{A4}α=↓|4R|β0z|gN|4α+↓|4
 5081  R|β1z|gN|gα+↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4R|βN|βα_↓|β1z
 5081  |g2|gN|gα_↓|g1|4α+↓|4O(z|g2|gN),>{A6}V|¬S(W|β1z|4α+↓|1|1|¬O|
 5082  4|¬O|4|¬O|1|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|4α=↓|4Q|β0|4α+↓|
 5082  4Q|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g
 5082  1|4α+↓|40(z|gN),>{A6}!!|πwhere |εV(x)|4α=↓|4x|4α+↓|4V|β2x|g2
 5084  |4α+↓|1|1|¬O|4|¬O|4|¬O |πand |εV|¬S(x)|4α=↓|41|4α+↓|42V|β2x|
 5086  4α+↓|1|1|¬O|4|¬O|4|¬O|4. |πThen set |εW|βN,|4.|4.|4.|4,|4W|β
 5089  2|βN|βα_↓|β1 |πto the coe∃cients in the power 
 5096  series|'{A6}|ε!!|(R|β0|4α+↓|4R|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1
 5097  α+↓|4R|βN|βα_↓|β1z|gN|gα_↓|g1|d2Q|β0|4α+↓|4Q|β1z|4α+↓|1|1|¬O
 5097  |4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g1|)|4α=↓|4W|βN|4α+
 5097  ↓|4W|βN|βα+↓|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4W|β2|βN|βα_↓|
 5097  β1z|gN|gα_↓|g1|4α+↓|4O(z|gN)|;{A6}!!|πand return 
 5100  to step N2.|'{A6}{IC}!|4|4|4|4The running time 
 5106  for this algorithm to obtain the coe∃cients up 
 5114  to |εN|4α=↓|42|gK |πis |εT(N), |πwhere|'{A6}|εT(2N)|4α=↓|4T(
 5119  N)|4α+↓|4(|πtime|4to|4do|4step|4N4|4α+↓|4|εO(N).|J!(17)|;
 5120  {A6}|πStraightforward algorithms for composition 
 5124  and division in step N4 will take order |εN|g3 
 5133  |πsteps, so Algorithm N will run slower than 
 5141  Algorithm T. However, Brent and Kung have found 
 5149  a way to do the required composition of power 
 5158  series with |εO(N|4|πlog|4|εN)|g3|g/|g2 |πarithmetic 
 5162  operations, and exercise 6 gives an even faster 
 5170  algorithm for division; hence (17) shows that 
 5177  power series reversion can be achieved by doing 
 5185  only |εO(N|4|πlog|4|εN)|g3|g/|g2 |πoperations 
 5188  as |εN|4|¬M|4|¬X. |π(On the other hand the constant 
 5196  of proportionality is such that |εN |πmust be 
 5204  really large before Algorithms L and T lose out 
 5213  to this ``high-speed'' method.)|'|εHistorical 
 5218  note|*/: |\|πJ. N. Bramhall and M. A. Chapple 
 5226  published the _rst |εO(n|g3) |πmethod for power 
 5233  series reversion [|εCACM |≡4 (1961), 317<318, 
 5239  503]; |πit was an o=-line algorithm whose running 
 5247  time was approximately the same as Algorithms 
 5254  L and T.|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11M29}|
 5258  9|1|≡1|≡.|9[|εM|*/|↔O|↔c|\] |πThe text explains 
 5262  how to divide |εU(z) |πby |εV(z) |πwhen |εV|β0|4|=|↔6α=↓|40;
 5269   |πhow should the division be done when |εV|β0|4α=↓|40?|'
 5278  {A3}|9|1|≡2|≡.|9[|*/|↔P|↔c|\] |πIf the coe∃cient 
 5282  of |εU(z) |πand |εV(z) |πare integers and |εV|β0|4|=|↔6α=↓|4
 5289  0, |πa recurrence relation for the integers |εV|urnα+↓1|)0|)
 5296  W|βn, |πwhere |εW|βn |πis de_ned by (3). How 
 5304  would you use this for power series division?|'
 5312  {A3}|9|1|≡3|≡.|9[|εM|*/|↔O|↔C|\] |πDoes formula 
 5315  (9) give the right results when |ε|≤a|4α=↓|40? 
 5322  |πWhen |ε|≤a|4α=↓|41?|'{A3}|9|1|≡4|≡.|9[HM|*/|↔P|↔L|\] 
 5325  |πShow that simple modi_cations of (9) can be 
 5333  used to calculate |εe|gV|g(|gz|g) |πand ln{H12}({H9}1|4α+↓|4
 5338  |εV(z){H12}){H9}, |πwhen |εV(z)|4α=↓|4V|β1z|4α+↓|4V|β2z|g2|4
 5340  α+↓|1|1|¬O|4|¬O|4|¬O|4.|'{A3}|9|1|≡5|≡.|9[M|*/|↔c|↔c|\] 
 5342  |πWhat happens when a power series is reverted 
 5350  twice; i.e., if the output of algorithm R or 
 5359  S is reverted again?|'{A3}|9|1|≡6|≡.|9[|εM|*/|↔P|↔O|\] 
 5364  |π(H. T. Kung.) Apply Newton's method to the 
 5372  computation of |εW(z)|4α=↓|41/V(z), |πwhen |εV(0)|4|=|↔6α=↓|
 5376  40, |πby _nding the power-series root of |εf|1(x)|4α=↓|4x|gα
 5383  _↓|g1|4α_↓|4V(z).|'{A3}|9|1|≡7|≡.|9[M|*/|↔P|↔L|\] 
 5385  |πUse Lagrange's inversion formula (12) to _nd 
 5392  a simple expression for the coe∃cient |εW|βn 
 5399  |πin the reversion of |εz|4α=↓|4t|4α_↓|4t|gm.|'
 5404  {A3}|9|1|≡8|≡.|9[M|*/|↔P|↔C|\] |πLagrange's inversion 
 5407  formula can be generalized as follows: If |εW(z)|4α=↓|4W|β1z
 5414  |4α+↓|4W|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4G|β1t|4α+↓|4G|
 5414  β2t|g2|4α+↓|4G|β3t|g3|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4G(t), 
 5415  |πwhere |εz |πand |εt |πare related by Eq. (10), 
 5424  then |εW|βn|4α=↓|4U|βn|βα_↓|β1/n |πwhere|'{A6}|εU|β0|4α+↓|4U
 5427  |β1z|4α+↓|4U|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4(G|β1|4α+↓
 5427  |42G|β2z|4α+↓|43G|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)(1|4α+↓|4V|β2
 5427  z|4α+↓|4V|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn.|;
 5428  {A6}|π(Equation (12) is the speical case |εG|β1|4α=↓|41, 
 5435  G|β2|4α=↓|4G|β3|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|40. 
 5436  |πThis equation can be proved, for example, by 
 5444  using tree-enumeration formulas as in exercise 
 5450  2.3.4.4<33.)|'!!|1|1Ecxtend algorithm L so that 
 5456  it obtains the coe∃cients |εW|β1, W|β2,|4.|4.|4.|4, 
 5462  |πin this more general situation, without substantially 
 5469  increasing its running time.|'{A3}|9|1|9|1|≡9|≡.|9[|ε|*/|↔O|↔
 5473  O|\] |πFind the values of |εT|βm|βn |πcomputed 
 5480  by Algorithm T as it determines the _rst _ve 
 5489  coe∃cients in the reversion of |εz|4α=↓|4t|4α_↓|4t|g2.|'
 5495  {A3}|≡1|≡0|≡.|9[M|*/|↔P|↔c|\] |πgiven that |εy|4α=↓|4x|g|≤a|4
 5498  α+↓|4a|β1x|ur|≤aα+↓2|)|)|4α+↓|1|1|¬O|4|¬O|4|¬O|4, 
 5499  |≤a|4|=|↔6α=↓|40, |πshow how to compute the coe∃cients 
 5506  in the expansion |εx|4α=↓|4y|g1|g/|g|≤a|4α+↓|4b|β2y|g2|g/|g|
 5509  ≤a|4α+↓|4b|β3y|g3|g/|g|≤a|4α+↓|1|1|¬O|4|¬O|4|¬O|4.|'
 5510  {A3}|≡1|≡1|≡.|9[M|*/|↔P|↔C|\] |πLet|'{A6}|εU(z)|4α=↓|4U|β0|4α
 5512  +↓|4U|β1z|4α+↓|4U|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O!|πand!|εV(z)|
 5512  4α=↓|4V|β1z|4α+↓|4V|β2z|g2|4α+↓|4V|β3z|g3|4α+↓|1|1|¬O|4|¬O|4
 5512  |¬O|4;|;{A6}|πdesign an algorithm which computes 
 5518  the _rst |εN |πcoe∃cients of |εU{H12}({H9}V(z){H12}){H9}.|'
 5524  {A3}|≡1|≡2|≡.|9[M|*/|↔P|↔c|\] |πFind a connection 
 5528  between polynomial division and power-series 
 5533  division: Given polynomials |εu(x) |πand |εv(x) 
 5539  |πof respective degrees |εm |πand |εn |πover 
 5546  a _eld, show how to _nd the polynomials |εq(x), 
 5555  r(x) |πsuch that |εu(x)|4α=↓|4q(x)v(x)|4α+↓|4r(x), 
 5559  |πdeg|ε(r)|4|¬W|4n, |πusing only operations on 
 5564  power series.|'{A24}|}|O|*/{H8L9M29}And it shall 
 5569  be,|?when thou hast made an end of reading this 
 5579  book,|?that thou shalt bind a stone to it,|?and 
 5589  cast it int*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
 5591